package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.List;

/**
 * 杨辉三角二
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/24 10:42
 */
public class E119 {
    // 1
    // 1 1
    // 1 2 1
    // 1 3 3 1
    // 1 4 6 4 1
    /**
     * <h3>方法一：迭代，一行一行生成</h3>
     * @param rowIndex 行索引,0开始
     * @return 返回当前行的内容
     */
    public List<Integer> getRow1(int rowIndex){
        List<List<Integer>> triangle = new ArrayList<>(rowIndex + 1);
        // 从0到rowIndex，生成杨辉三角
        for (int i = 0; i <= rowIndex; i++) {
            // 先初始化当前行
            triangle.add(new ArrayList<>(i + 1));
            // 如果当前行是0，则添加一个1
            if (i == 0){
                triangle.get(i).add(1);
            }
            // 否则综合上一行的内容填充当前行
            else {
                for (int j = 0; j <= i; j++) {
                    if (j == 0 || j == i){
                        triangle.get(i).add(1);
                    }else {
                        triangle.get(i).add(triangle.get(i - 1).get(j - 1) + triangle.get(i - 1).get(j));
                    }
                }
            }
        }
        return triangle.get(rowIndex);
    }

    // 1
    // 1 1
    // 1 2 1
    // 1 3 3 1
    // 1 4 6 4 1
    /**
     * <h3>方法二：递归实现</h3>
     * @param rowIndex 当前行
     * @return 当前行的内容
     */
    public List<Integer> getRow2(int rowIndex) {
        ArrayList<Integer> currentRow = new ArrayList<>();
        // 递归结束条件：行的索引为0
        if (rowIndex == 0){
            currentRow.add(1);
            return currentRow;
        }
        // 递的时候确定上一行的内容
        List<Integer> lastRow = getRow2(rowIndex - 1);
        // 归的时候确定当前行的内容
        for (int i = 0; i <= rowIndex; i++) {
            if (i == 0 || i == rowIndex){
                currentRow.add(1);
            }else {
                currentRow.add(lastRow.get(i - 1) + lastRow.get(i));
            }
        }
        // 返回当前行
        return currentRow;
    }

    // C(0,0)
    // C(1,0) C(1,1)
    // C(2,0) C(2,1) C(2,2)
    // C(3,0) C(3,1) C(3,2) C(3,3)
    // C(4,0) C(4,1) C(4,2) C(4,3) C(4,4)
    // C(5,0) C(5,1) C(5,2) C(5,3) C(5,4) C(5,5)

    /**
     * <h3>方法三：用数学的组合数解决</h3>
     * @param rowIndex 行索引
     * @return 返回当前行的内容
     */
    public List<Integer> getRow3(int rowIndex){
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i <= rowIndex; i++) {
            result.add((int) combination(rowIndex, i));
        }
        return result;
    }

    /**
     * <h3>方法四：采用C(n, m - 1)和C(n, m)之间的关系进行求解</h3>
     * @param rowIndex 行索引
     * @return 返回当前行的内容
     */
    public List<Integer> getRow4(int rowIndex){
        List<Integer> result = new ArrayList<>(rowIndex + 1);
        result.add(1); // 第一个元素为1
        for (int i = 1; i <= rowIndex; i++) {
            // C(n, i - 1) = n / 1 * (n - 1) / 2 * …… * (n - i + 2) / i - 1
            // C(n, i) = n / 1 * (n - 1) / 2 * …… * (n - i + 1) / i
            // C(n, i) 相比于 C(n, i - 1)，多乘了一个 (n - i + 1) / i
            result.add((int) ((long) result.get(i - 1) * (rowIndex - i + 1) / i)); // 溢出的时候用long运算，除完后转回int，保证不会越界
        }
        return result;
    }

    /**
     * 计算阶乘
     * @param n 阶乘的参数
     * @return 结果
     */
    private long factorial(int n){
        if (n == 1 || n == 0){
            return 1;
        }
        return n * factorial(n - 1);
    }

    /**
     * 计算组合数C(n, m)，优化后的，没有用阶乘
     * @param n 总数
     * @param m 选择的个数
     * @return 组合数
     */
    private long combination(int n, int m){
        if (m > n) {
            return 0;
        }
        if (m == 0 || m == n) {
            return 1;
        }
        m = Math.min(m, n - m); // C(n, m) = C(n, n - m)，选最小的计算快
        long result = 1;
        for (int i = 0; i < m; i++) {
            // C(n, m) == n / m * C(n - 1, m - 1)
            //         == n / m * (n - 1) / (m - 1) * C(n - 2, m - 2)
            //         == n / m * (n - 1) / (m - 1) * (n - 2) / (m - 2) * ... (n - m + 1) / (m - m + 1) * C(n - m, 0)
            //         == n / m * (n - 1) / (m - 1) * (n - 2) / (m - 2) * ... (n - m + 1) / (1) * 1
            //         == n * (n - 1) * ... (n - m + 1) / m! (分母的数字换位置)
            //         == n / 1 * (n - 1) / 2 * ... (n - m + 1) / m（这一部分就是下面的原理）
            result = result * (n - i) / (i + 1);
        }
        return result;
    }

    /**
     * <h3>方法五：动态规划，这里直接就用优化的一维数组了</h3>
     * @param rowIndex 行索引,0开始
     * @return 返回当前行的内容
     */
    public List<Integer> getRow5(int rowIndex){
        int[] dp = new int[rowIndex + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = i; j >= 0; j--) {
                if (j == 0 || i == j){
                    dp[j] = 1;
                }else {
                    dp[j] = dp[j - 1] + dp[j];
                }
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int j : dp) {
            result.add(j);
        }
        return result;
    }
}
